#include "Calculate.h"

Calculate::Calculate() {
    FlightData.resize(1); QueryPointData.resize(1); //QueryPointData_Point.resize(1);
    FlightData[0].push_back(L"飞行线编号"); FlightData[0].push_back(L"飞行线端点1坐标"); FlightData[0].push_back(L"飞行线端点2坐标"); //FlightData[0].push_back(L"查询点到飞行线距离");
    QueryPointData[0].push_back(L"查询点坐标"); QueryPointData[0].push_back(L"距离最近的飞行线编号"); QueryPointData[0].push_back(L"距离大小");
    //QueryPointData_Point[0].push_back(L"查询点坐标");
}

int Calculate::Get_Flight_num() {
    return Flight_num;
}

int Calculate::Get_QueryPoint_num() {
    return QueryPoint_num;
}

int Calculate::GetCurrentLine() {
    return currentLine;
}

void Calculate::Get_FlightDataReference(vector<vector<wstring>>& newdata) {
    newdata = FlightData;
}

void Calculate::Get_QueryPointDataReference(vector<vector<wstring>>& newdata) {
    newdata = QueryPointData;
}

void Calculate::Get_QueryPointData_PointReference(vector<vector<wstring>>& newdata) {
    newdata.resize(QueryPoint_num + 1);
    newdata[0].push_back(L"查询点坐标");
    for (int i = 1; i <= QueryPoint_num; ++i) {
        newdata[i].push_back(QueryPointData[i][0]);
    }
    return;

    //newdata = QueryPointData_Point;
}








std::pair<double, double> Calculate::findClosestPointOnSegment(double Px, double Py,
    double Ax, double Ay,
    double Bx, double By) const {
    // 向量AB
    double ABx = Bx - Ax;
    double ABy = By - Ay;

    // 向量AP
    double APx = Px - Ax;
    double APy = Py - Ay;

    // 计算AB长度的平方
    double AB2 = ABx * ABx + ABy * ABy;

    // 计算AP与AB的点积
    double AP_AB = APx * ABx + APy * ABy;

    // 计算参数t，表示最近点在线段AB上的位置比例
    double t = AP_AB / AB2;

    // 检查最近点是否在线段上
    if (t <= 0.0) {
        // 最近点是A点
        return std::make_pair(Ax, Ay);
    }
    else if (t >= 1.0) {
        // 最近点是B点
        return std::make_pair(Bx, By);
    }
    else {
        // 垂足在线段上
        return std::make_pair(Ax + t * ABx, Ay + t * ABy);
    }
}

// 共用的数据结构初始化
void Calculate::InitDataStructures(
    int flight_num,
    int query_point_num,
    bool resizeFlightLines
    ){
    int final_flight_num = (flight_num == -1) ? Flight_num : flight_num;
    int final_query_num = (query_point_num == -1) ? QueryPoint_num : query_point_num;


    FlightData.resize(final_flight_num + 1);
    for (int i = 1; i < FlightData.size(); ++i) {
        FlightData[i].clear();
    }
    QueryPointData.resize(final_query_num + 1);
    for (int i = 1; i < QueryPointData.size(); ++i) {
        QueryPointData[i].clear();
    }

    if (resizeFlightLines) {
        FlightLines.clear();
        FlightLines.resize(final_flight_num);
        QueryPoints.clear();
        QueryPoints.resize(final_query_num);
    }
}

void Calculate::ProcessFlightLine(int id, int x1, int y1, int x2, int y2) {
    FlightLines[id - 1] = { id, x1, y1, x2, y2 };

    wstring xy1 = L"(" + to_wstring(x1) + L"," + to_wstring(y1) + L")";
    wstring xy2 = L"(" + to_wstring(x2) + L"," + to_wstring(y2) + L")";

    FlightData[id].push_back(to_wstring(id));
    FlightData[id].push_back(xy1);
    FlightData[id].push_back(xy2);
}

void Calculate::ProcessQueryPoint(int id, int x, int y) {
    QueryPoints[id - 1] = { x, y };

    wstring xy = L"(" + to_wstring(x) + L"," + to_wstring(y) + L")";
    QueryPointData[id].push_back(xy);
}

int Calculate::ReadDataFile(wstring filePath) {
    //判断传入的文件路径是不是.txt或.csv
    if (!IsSupportedFile(filePath)) return -1;//如果不是则提示用户传入.txt或.csv文件
    wifstream file(filePath);
    if (!file.is_open()) {
        return 0; // 文件打开失败
    }
    try {
        // 根据扩展名处理
        size_t dotPos = filePath.find_last_of(L".");
        std::wstring ext = filePath.substr(dotPos + 1);
        std::transform(ext.begin(), ext.end(), ext.begin(), ::towlower);

        if (ext == L"txt") {
            return ReadTextFile(file);
        }
        else if (ext == L"csv") {
            return ReadCSVFile(file);
        }
    }
    catch (...) {
        return -404; // 未知错误
    }
    return -2;  //文件打得开，但不是txt和csv文件 


}

// CSV行分割辅助函数
vector<wstring> Calculate::SplitCSVLine(const wstring& line) {
   vector<wstring> result;
   wstringstream ss(line);
   wstring field;

     while (std::getline(ss, field, L',')) {
        // 去除首尾空格
        size_t start = field.find_first_not_of(L" ");
        size_t end = field.find_last_not_of(L" ");
        if (start != std::wstring::npos && end != std::wstring::npos) {
            result.push_back(field.substr(start, end - start + 1));
        } else {
            result.push_back(L""); // 空字段
        }
    }
    return result;
}

int Calculate::ReadCSVFile(wifstream& file) {
    wstring line;
    // 读取首行：飞行线数量,查询点数量
    if (!std::getline(file, line)) return -3;
    vector<wstring> header = SplitCSVLine(line);
    if (header.size() != 2) return -3;
    try {
        Flight_num = std::stoi(header[0]);
        QueryPoint_num = std::stoi(header[1]);
    }
    catch (...) {
        return -3; // 数值转换失败
    }
    // 验证数量有效性
    if (Flight_num <= 0 || QueryPoint_num <= 0) return -3;
    //// 初始化数据结构
    InitDataStructures();

    // 读取飞行线数据
    for (int i = 1; i <= Flight_num; ++i) {
        if (!getline(file, line)) return -3;
        vector<wstring> parts = SplitCSVLine(line);
        if (parts.size() != 4) return -3;

        try {
            int x1 = stoi(parts[0]);
            int y1 = stoi(parts[1]);
            int x2 = stoi(parts[2]);
            int y2 = stoi(parts[3]);
            ProcessFlightLine(i, x1, y1, x2, y2);
        }
        catch (...) {
            return -3; // 坐标转换失败
        }
    }

    // 读取查询点数据
    for (int i = 1; i <= QueryPoint_num; ++i) {
        if (!getline(file, line)) return -3;
        vector<wstring> parts = SplitCSVLine(line);
        if (parts.size() != 2) return -3;

        try {
            double x = stod(parts[0]);
            double y = stod(parts[1]);
            ProcessQueryPoint(i, x, y);
        }
        catch (...) {
            return -3; // 坐标转换失败
        }
    }

    findNearestFlightLineKDTree(FlightLines, QueryPoints);
    return 1;
}

int Calculate::ReadTextFile(wifstream& file) {
    wstring line;

    if (!getline(file, line)) return -3;
    wistringstream header(line);
    if (!(header >> Flight_num >> QueryPoint_num)) return -3;
    // 验证数量有效性
    if (Flight_num < 0 || QueryPoint_num < 0) return -3;
    InitDataStructures();

        for (int i = 1; i <= Flight_num; ++i) {
            if (!getline(file, line)) return -3;
            wistringstream ss(line);
            int four = 4, x1, y1, x2, y2;
            if (!(ss >> x1 >> y1 >> x2 >> y2)) return -3;
            // 检查多余数据
            wstring temp;
            if (ss >> temp) return -3;
            ProcessFlightLine(i, x1, y1, x2, y2);
        }
        for (int i = 1; i <= QueryPoint_num; ++i) {
            //QueryPointData[i].push_back(to_wstring(i)); //编号输入
            if (!getline(file, line)) return -3;
            wistringstream ss(line);
            int two = 2, x, y;
            if (!(ss >> x >> y)) return -3;
            // 检查多余数据
            wstring temp;
            if (ss >> temp) return -3;
            ProcessQueryPoint(i, x, y);
        }

    //for (int i = 0; i < QueryPoints.size(); ++i) {
    //    cout << QueryPoints[i].x << " " << QueryPoints[i].y << "\n";
    //}
    //findNearestFlightLine(FlightLines, QueryPoints);


    /* results = findNearestFlightLine(FlightLines,QueryPoints);
     for (int i = 1; i <= results.size(); ++i) {
         QueryPointData[1].push_back(to_wstring(results[i]));
         QueryPointData[1].push_back();
     }
     */
    findNearestFlightLineKDTree(FlightLines, QueryPoints);
    return 1; //返回1表示成功
}

void Calculate::FinishDirectInput(){
    int linenumber = DirectlyInputFlightLines.size();
    int quertnumber = DirectlyInputQueryPoints.size();

    Flight_num = linenumber;
    QueryPoint_num = quertnumber;
    InitDataStructures();

    for (int i = 1; i <=linenumber; ++i) {

        FlightLines[i - 1] = {
            i, 
            DirectlyInputFlightLines[i-1].x1,
            DirectlyInputFlightLines[i-1].y1,
            DirectlyInputFlightLines[i-1].x2,
            DirectlyInputFlightLines[i-1].y2
        };
        FlightLines[i-1].id = i;
        wstring xy1 = L"(" + to_wstring(DirectlyInputFlightLines[i-1].x1) + L"," + to_wstring(DirectlyInputFlightLines[i-1].y1) + L")";
        wstring xy2 = L"(" + to_wstring(DirectlyInputFlightLines[i-1].x2) + L"," + to_wstring(DirectlyInputFlightLines[i-1].y2) + L")";
        FlightData[i].push_back(to_wstring(i));
        FlightData[i].push_back(xy1);
        FlightData[i].push_back(xy2);
    }
    for (int i = 1; i <= quertnumber; ++i) {
        QueryPoints[i - 1] = { DirectlyInputQueryPoints[i-1].x, DirectlyInputQueryPoints[i-1].y};

        wstring xy = L"(" + to_wstring(DirectlyInputQueryPoints[i-1].x) + L"," + to_wstring(DirectlyInputQueryPoints[i-1].y) + L")";
        QueryPointData[i].push_back(xy);
    }
    findNearestFlightLineKDTree(FlightLines, QueryPoints);
}

// 构建KD树
shared_ptr<KDNode> Calculate::buildKDTree(vector<FlightLine>& flightLines, int depth) {
    if (flightLines.empty()) return nullptr;

    // 选择分割轴（交替按x或y轴分割）
    int axis = depth % 2;

    // 按当前轴排序
    sort(flightLines.begin(), flightLines.end(), [axis](const FlightLine& a, const FlightLine& b) {
        double a_mid = (axis == 0) ? (a.x1 + a.x2) / 2 : (a.y1 + a.y2) / 2;
        double b_mid = (axis == 0) ? (b.x1 + b.x2) / 2 : (b.y1 + b.y2) / 2;
        return a_mid < b_mid;
        });

    // 取中点作为当前节点
    int mid = flightLines.size() / 2;
    double mid_x = (flightLines[mid].x1 + flightLines[mid].x2) / 2;
    double mid_y = (flightLines[mid].y1 + flightLines[mid].y2) / 2;
    auto node = make_shared<KDNode>(mid_x, mid_y, flightLines[mid].id);

    // 递归构建左右子树
    vector<FlightLine> leftLines(flightLines.begin(), flightLines.begin() + mid);
    vector<FlightLine> rightLines(flightLines.begin() + mid + 1, flightLines.end());
    node->left = buildKDTree(leftLines, depth + 1);
    node->right = buildKDTree(rightLines, depth + 1);

    return node;
}

// 计算两点距离的平方（避免开方提高效率）
double Calculate::distanceSquared(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return dx * dx + dy * dy;
}

// KD树最近邻搜索
void Calculate::nearestNeighborSearch(shared_ptr<KDNode> node, const QueryPoint& query, int depth, double& minDist, int& nearestId) {
    if (!node) return;

    double currentDist = distanceSquared(query.x, query.y, node->point[0], node->point[1]);
    if (currentDist < minDist) {
        minDist = currentDist;
        nearestId = node->id;
    }

    int axis = depth % 2;
    bool goLeft = (axis == 0) ? (query.x < node->point[0]) : (query.y < node->point[1]);

    // 优先搜索更可能包含最近邻的分支
    if (goLeft) {
        nearestNeighborSearch(node->left, query, depth + 1, minDist, nearestId);
    }
    else {
        nearestNeighborSearch(node->right, query, depth + 1, minDist, nearestId);
    }

    // 检查另一分支是否可能有更近的点
    double remainingDist = (axis == 0) ?
        (query.x - node->point[0]) * (query.x - node->point[0]) :
        (query.y - node->point[1]) * (query.y - node->point[1]);
    if (remainingDist < minDist) {
        if (goLeft) {
            nearestNeighborSearch(node->right, query, depth + 1, minDist, nearestId);
        }
        else {
            nearestNeighborSearch(node->left, query, depth + 1, minDist, nearestId);
        }
    }
}

// 计算点到线段的最短距离（与之前相同）
double Calculate::pointToLineDistance(double px, double py, double x1, double y1, double x2, double y2) {
    double dx = x2 - x1;
    double dy = y2 - y1;
    double lineLengthSq = dx * dx + dy * dy;

    if (lineLengthSq == 0) {
        return sqrt((px - x1) * (px - x1) + (py - y1) * (py - y1));
    }

    double t = ((px - x1) * dx + (py - y1) * dy) / lineLengthSq;
    t = max(0.0, min(1.0, t));

    double projectionX = x1 + t * dx;
    double projectionY = y1 + t * dy;

    return sqrt((px - projectionX) * (px - projectionX) + (py - projectionY) * (py - projectionY));
}

// 使用KD树优化查找最近飞行线
vector<int> Calculate::findNearestFlightLineKDTree(const vector<FlightLine>& flightLines, const vector<QueryPoint>& queryPoints) {
    // 构建KD树（需要非const，所以复制一份）
    vector<FlightLine> linesCopy = flightLines;
    auto root = buildKDTree(linesCopy);
    int num = 1; //后加入的代码
    vector<int> results;
    for (const auto& qp : queryPoints) {
        #undef max 
        double minDist = std::numeric_limits<double>::max();
        int nearestId = -1;

        // 先用KD树找到最近的中点（近似解）
        nearestNeighborSearch(root, qp, 0, minDist, nearestId);

        // 由于KD树存储的是中点，我们需要在所有飞行线中精确计算距离
        // 但可以只检查KD树返回的候选飞行线，减少计算量
        #undef max 
        double exactMinDist = std::numeric_limits<double>::max();
        int exactNearestId = -1;
        for (const auto& line : flightLines) {
            double dist = pointToLineDistance(qp.x, qp.y, line.x1, line.y1, line.x2, line.y2);
            if (dist < exactMinDist) {
                exactMinDist = dist;
                exactNearestId = line.id;
            }
        }
        QueryPointData[num].push_back(to_wstring(exactNearestId));  //后加入的代码
        QueryPointData[num].push_back(to_wstring(exactMinDist));//后加入的代码
        results.push_back(exactNearestId);
        ++num; //后加入的代码
    }
    return results;
}

//// 插入新的飞行线到 KD 树
//std::shared_ptr<KDNode> Calculate::InsertFlightLine(std::shared_ptr<KDNode> node, const FlightLine& line, int depth = 0) {
//    if (!node) {
//        // 计算飞行线的中点作为节点的坐标
//        double midX = (line.x1 + line.x2) / 2;
//        double midY = (line.y1 + line.y2) / 2;
//        return std::make_shared<KDNode>(midX, midY, line.id);
//    }
//
//    int axis = depth % 2;
//    double newPoint = (axis == 0) ? (line.x1 + line.x2) / 2 : (line.y1 + line.y2) / 2;
//    double currentPoint = node->point[axis];
//
//    if (newPoint < currentPoint) {
//        node->left = InsertFlightLine(node->left, line, depth + 1);
//    }
//    else {
//        node->right = InsertFlightLine(node->right, line, depth + 1);
//    }
//
//    return node;
//}
//

//暴力方法求解最近飞行线
void Calculate::findNearestFlightLine(const vector<FlightLine>& flightLines, const vector<QueryPoint>& queryPoints) {
    vector<int> results;
    int num = 1; //后加入的代码
    for (const auto& qp : queryPoints) {
        double minDistance = 1.7976931348623157e+308;
        int nearestLineId = -1;
        for (const auto& line : flightLines) {
            double distance = pointToLineDistance(qp.x, qp.y, line.x1, line.y1, line.x2, line.y2);
            if (distance < minDistance) {
                minDistance = distance;
                nearestLineId = line.id;
            }
        }
        QueryPointData[num].push_back(to_wstring(nearestLineId));  //后加入的代码
        QueryPointData[num].push_back(to_wstring(minDistance));//后加入的代码
        results.push_back(nearestLineId);
        ++num; //后加入的代码
    }
    return;
    //return results;
}

